#include "DfsVisitor.h"
#include "Algorithms.h"
#include <algorithm>

#define INF 1000000000

void DfsTopologicalSort::preInit(const std::unique_ptr<IDigraph> &graph)
{
	_global_visited.clear();
	_global_visited.resize(graph->getNumberOfVertices(), false);
	_edge_process_order.clear();
	_has_loop = false;
	_sorted_order.clear();
}

void DfsTopologicalSort::initialize(const std::unique_ptr<IDigraph> &graph, int start_vertex)
{
	_on_stack.resize(graph->getNumberOfVertices(), false);
	_visited_vertices.resize(graph->getNumberOfVertices(), false);
}

void DfsTopologicalSort::comeToVertex(int vertex)
{
	if (!_global_visited[vertex])
	{
		_global_visited[vertex] = true;
		_on_stack[vertex] = true;
	}
}

void DfsTopologicalSort::processEdge(int from, int to)
{
	_edge_process_order.push_back(Edge(from, to));
	if (_on_stack[to]) _has_loop = true;
}

void DfsTopologicalSort::leaveVertex(int vertex)
{
	_sorted_order.push_back(vertex);
	_on_stack[vertex] = false;
}

void DfsTopologicalSort::finalize()
{

}

bool DfsTopologicalSort::isVisited(int vertex)
{
	return _global_visited[vertex];
}

bool DfsTopologicalSort::hasLoop()
{
	return _has_loop;
}

std::vector<Edge> DfsTopologicalSort::getProcessOrder()
{
	return _edge_process_order;
}

std::vector<int> DfsTopologicalSort::getSortedOrder()
{
	std::reverse(_sorted_order.begin(), _sorted_order.end());
	return _sorted_order;
}

void DfsTarjan::preInit(const std::unique_ptr<IDigraph> &graph)
{
	_in_times.clear();
	_in_times.resize(graph->getNumberOfVertices(), INF);
	_farthest.clear();
	_farthest.resize(graph->getNumberOfVertices(), INF);
	_buffered.clear();
	_buffered.resize(graph->getNumberOfVertices(), false);
	_ancestor.clear();
	_ancestor.resize(graph->getNumberOfVertices(), -1);
	_components.clear();
	_buffer.clear();
	_cur_time = 0;
}

std::vector<std::vector<int> > DfsTarjan::getStronglyConnectedComponents(const std::unique_ptr<IDigraph> &graph)
{
	std::unique_ptr<DfsVisitor> solution(this);
	dfs(graph, solution);
	solution.release();
	return _components;
}

void DfsTarjan::initialize(const std::unique_ptr<IDigraph> &graph, int start_vertex)
{

}

void DfsTarjan::comeToVertex(int vertex)
{
	if (_in_times[vertex] == INF)
	{
		_cur_time++;
		_in_times[vertex] = _cur_time;
		_farthest[vertex] = _cur_time;
		_buffer.push_back(vertex);
		_buffered[vertex] = true;
	}
}

void DfsTarjan::processEdge(int from, int to)
{
	if (_buffered[to])
		_farthest[from] = std::min(_farthest[from], _in_times[to]);
	if (_ancestor[to] == -1)
		_ancestor[to] = from;
}

void DfsTarjan::leaveVertex(int vertex)
{
	if (_ancestor[vertex] != -1 && _ancestor[vertex] != -2)
		_farthest[_ancestor[vertex]] = std::min(_farthest[_ancestor[vertex]], _farthest[vertex]),
		_ancestor[vertex] = -2;

	if (_farthest[vertex] == _in_times[vertex])
	{
		_components.push_back(std::vector<int>(0));
		int added_vertex;
		do
		{
			added_vertex = _buffer.back();
			_buffer.pop_back();
			_buffered[added_vertex] = false;
			_components[_components.size() - 1].push_back(added_vertex);
		} while (added_vertex != vertex);
	}
}

void DfsTarjan::finalize()
{

}

std::unique_ptr<IDigraph> DfsTarjan::getCondesedGraph(const std::unique_ptr<IDigraph> &graph)
{
	std::vector<std::vector<int> > comps = getStronglyConnectedComponents(graph);
	std::vector<int> color(graph->getNumberOfVertices());
	for (size_t i = 0; i < comps.size(); i++)
		for (size_t j = 0; j < comps[i].size(); j++)
			color[comps[i][j]] = i;
	std::vector<Edge> edges;
	for (int i = 0; i < graph->getNumberOfVertices(); i++)
	{
		std::vector<int> adjacent = graph->getIncidenceList(i);
		for (size_t j = 0; j < adjacent.size(); j++)
			if (color[i] != color[adjacent[j]])
				edges.push_back(Edge(color[i], color[adjacent[j]]));
	}
	sort(edges.begin(), edges.end());
	int real_size = 1;
	for (size_t i = 1; i < edges.size(); i++)
		if (edges[i].begin != edges[real_size - 1].begin || edges[i].end != edges[real_size - 1].end)
			edges[real_size++] = edges[i];
	return makeCompactGraph(edges, comps.size());
}

std::vector<int> DfsTarjan::getVerticesColors(const std::unique_ptr<IDigraph> &graph)
{
	std::vector<std::vector<int> > comps = getStronglyConnectedComponents(graph);
	std::vector<int> color(graph->getNumberOfVertices());
	for (size_t i = 0; i < comps.size(); i++)
		for (size_t j = 0; j < comps[i].size(); j++)
			color[comps[i][j]] = i;
	return color;
}

std::vector<int> DfsTarjan::getExactComponent(const std::unique_ptr<IDigraph> &graph, int vertex)
{
	std::vector<std::vector<int> > comps = getStronglyConnectedComponents(graph);
	for (size_t i = 0; i < comps.size(); i++)
		for (size_t j = 0; j < comps[i].size(); j++)
			if (comps[i][j] == vertex) return comps[i];
	return std::vector<int>(0);
}

std::vector<int> DfsTarjan::getSortedCondesedGraph(const std::unique_ptr<IDigraph> &graph)
{
	std::unique_ptr<IDigraph> condensed = getCondesedGraph(graph);
	std::unique_ptr<DfsVisitor> sorter(new DfsTopologicalSort());
	dfs(condensed, sorter);
	std::vector<int> order = dynamic_cast<DfsTopologicalSort*>(sorter.get())->getSortedOrder();
	return order;
}

#undef INF